1. Field of the Invention
The present invention relates to a technique for determining a next forwarding destination of a data signal composed of a sequence of bits such as an IP (Internet protocol) packet on the basis of a destination address included in the data signal such as an IP address.
2. Description of the Related Art
There has been a router, which is a retrieval device for retrieving route information indicating the outgoing link to be used to forward an incoming data signal such as an IP packet to a communication network. Provided with a data signal, the router retrieves route information from a retrieval table and places the data signal into an appropriate outgoing queue depending on the retrieved route information.
In general, the retrieval table registers an xe2x80x9coutput interfacexe2x80x9d or an xe2x80x9cIP address of a router as the next transit destinationxe2x80x9d, which is the next forwarding destination of an incoming IP packet signal and is associated with an xe2x80x9cIP sub-net address"" and a xe2x80x9cprefix lengthxe2x80x9d included in the IP packet signal.
The router retrieves route information from the retrieval table by using an IP address indicating the ultimate destination of the incoming IP packet signal as a retrieval key, and determines a forwarding destination such as xe2x80x9coutput interfacexe2x80x9d. In this retrieval, the router uses the longest matching method to determine an IP sub-net address which is a best match with the IP address of the incoming IP packet among IP sub-net addresses registered in the retrieval table.
Here, the longest matching method will be described briefly. In the longest matching method among the registered IP addresses, one having the longest significant bit string matching with the IP address of the retrieval key is selected. For example, it is assumed that two IP addresses xe2x80x9c0**xe2x80x9d and xe2x80x9c00*xe2x80x9d have been registered as IP addresses each being 3 bits in bit length.
As for xe2x80x9c0**,xe2x80x9d only the head bit xe2x80x9c0xe2x80x9d has an effective bit value. Each of the second and subsequent bits xe2x80x9c**xe2x80x9d represents an arbitrary value of xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d. As for xe2x80x9c00*,xe2x80x9d the first and second bits xe2x80x9c00xe2x80x9d are effective bit values, and the third bit xe2x80x9c*xe2x80x9d represents an arbitrary value of xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d. Hereinafter, the length of an significant bit string of an address in bit-count representation is referred to as prefix length (significant bit string length).
The IP address which indicates the ultimate destination of the outgoing IP packet and is used as the retrieval key is compared with two registered IP addresses. If the IP address of the retrieval key is xe2x80x9c0001 . . . xe2x80x9d, xe2x80x9c00*xe2x80x9d is longer than xe2x80x9c0**xe2x80x9d in prefix length matching the registered IP address. In this case, therefore, xe2x80x9c00*xe2x80x9d is selected as the IP address of the next forwarding destination.
In the case where the number of bits of the IP address is as short as 3 bits as in the above-described example, its retrieval is also easy. However, the number of bits of actually used IP address is far greater than the above example. For example, the address length defined in the standards IPv4 (Internet Protocol, version 4) is 32 bits. Further, in IPv6 (Internet Protocol, version 6) standardized in recent years, the address length becomes as long as 128 bits. In the data signal transit processing in the router, therefore, efficiency improvement of the search processing becomes important.
There have been proposed various methods of retrieving the next forwarding destination of an IP packet on the basis of the IP address included in the IP packet signal with improved efficiency of searching.
First, a binary tree retrieval method will now be described briefly by referring to FIG. 1.
FIG. 1 is a concept diagram showing a binary tree retrieval method. In the example as shown in FIG. 1, registered IP addresses P1 to P8 are formed in tree structure in the binary tree retrieval method, bit values of a bit string are successively compared by taking a bit as a unit. As shown in FIG. 1, therefore, nodes forming the tree correspond to bit values of the bit string. respectively.
In the binary tree retrieval method, however, an increase in the number of entries causes a rapid increase in the number of nodes. As a result, the number of retrieval times also increases rapidly. As a retrieval method capable of suppressing the increase of the number of retrieval times caused by the increases of nodes, therefore, a radix tree retrieval method has been proposed.
The radix tree retrieval method will now be described simply by referring to FIG. 2. In the example as shown in FIG. 2, registered IP addresses P1 to P8 are formed in a tree structure. Unlike the binary tree retrieval method, it is not necessary to dispose nodes of the tree structure by taking a bit as a unit, in the radix tree retrieval method. Therefore, the number of nodes in the radix tree retrieval method is suppressed to twice the number of entries (the number of registered IP addresses) at most.
In the radix tree retrieval method, xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d of a branch of the tree structure does not directly represent bit values of a bit string. In each node, therefore, it is necessary to compare the entry of the node with the retrieval key.
Further, in the radix tree retrieval method, the number of retrieval times varies according to the. distribution of bits of a registered IP address. And the maximum number of retrieval times becomes, the same as the number of bits of a bit string in some cases. For example. in IPv4 in which the number of assigned bits is 32, the number of retrieval times may be 32.
Therefore, an example of a retrieval method capable of further suppressing the increase of the number of retrieval times caused by an increase of nodes has been proposed as a controlled prefix expansion retrieval method (hereafter simply referred to as xe2x80x9cexpansion methodxe2x80x9d) in Reference 1: xe2x80x9cACM SIGMETRICSxe2x80x9d 98 pp. 1 to 10. June 1998xe2x80x9d. A retrieve method similar to this expansion method is disclosed in Reference 2: Japanese Patent Application Laid-Open Publication No. 10-257066.
The conventional expansion method will now be described by referring to FIG. 3. In the conventional expansion method, the bit string of an IP address is divided into a plurality of divisional bit strings, and retrieval tables (xe2x80x9ccontrol tablesxe2x80x9d in the Reference 2) are provided for respective hierarchical divisional bit strings. In each retrieval table, each divisional bit string is used as an entry address.
In the example as shown in FIG. 3, a bit string having a total of 7 bits is successively divided into three divisional bit strings which have 2 bits, 3 bits and 2 bits, respectively. In retrieval tables at first and third stages, four divisional bit strings xe2x80x9c00xe2x80x9d to xe2x80x9c11xe2x80x9d are used as the entry addresses. In a retrieval table at a second stage, eight divisional bit strings xe2x80x9c000xe2x80x9d to xe2x80x9c111xe2x80x9d are used as entry addresses.
When updating the registered addresses in the expansion method, a retrieval end/continuation flag, a next table pointer indicating the IP address of a next forwarding destination, and transmission interface information itself are set in all registrable entries among entries of the retrieval table.
In other words, when registering an IP address, a bit string of an entry shorter than the bit length of each divisional bit string in each retrieval table is expanded to the end of the divisional bit string. By expanding the bit string, a plurality of entries sharing the bit string before expansion are caused to correspond commonly to the registered IP address.
In the example shown in FIG. 3, each of registered IP addresses P1 to P8 is expanded to the least significant bit of each divisional bit string. For example, the IP address xe2x80x9c0*xe2x80x9d indicated by P5 having a prefix length of 1 is expanded by 1 bit, and become xe2x80x9c00xe2x80x9d and xe2x80x9c01xe2x80x9d each having a length of 2 bits. And in the retrieval table of the first stage, P5 is registered in both entries which have entry addresses xe2x80x9c00xe2x80x9d and xe2x80x9c01xe2x80x9d, respectively.
In the case where the IP address xe2x80x9c111*xe2x80x9d of P2 having a prefix length of xe2x80x9c3xe2x80x9d is expanded by 2 bits, the IP address xe2x80x9c111*xe2x80x9d of P2 become sour entries xe2x80x9c11100,xe2x80x9d xe2x80x9c11101,xe2x80x9d xe2x80x9c11110,xe2x80x9d and xe2x80x9c11111xe2x80x9d each having a length of 5 bits. And in the retrieval table at the second stage, a divisional bit string of the third to fifth bits becomes an entry address. In four entries of entry addresses xe2x80x9c100,xe2x80x9d xe2x80x9c101,xe2x80x9d xe2x80x9c110,xe2x80x9d and xe2x80x9c111,xe2x80x9d therefore, P2 is registered. In addition, other registered IP addresses are expanded in the same way, and registering is conducted.
By expanding the bit strings, registered IP addresses can thus be associated with specific entry addresses of retrieval tables. In retrieval of the retrieval table at each stage, therefore, a divisional bit string of a registered IP address as it is can be used as an offset.
Therefore, the comparison with an entry in each node required in the radix tree retrieval becomes unnecessary. And the number of retrieval times is equal to the number of stages of the retrieval tables at most. For example, in the example of FIG. 3, the respective retrieval tables at three stages are provided and consequently the number of retrieval times is three at most. By using the expansion method, therefore, the number of retrieval times can be reduced significantly.
Further, if an IP address corresponding to the IP address of the retrieval key is not yet registered, then it is also possible to register the IP address of the retrieval key in the retrieval table.
It is now assumed that a 32-bit IP address is divided into four divisional bit strings each having 8 bits. How to register an IP address by using the expansion method in this case will now be described by referring to FIGS. 4 and 5.
FIG. 4 shows a procedure for registering an IP address in the case where the IP address to be registered has a prefix length of 8 bits or less. In this case, registration is conducted only for the retrieval table at the first stage (first control table). In registering such a range of entries of the first control that the IP address can be registered therein is first determined (step S1 of FIG. 4).
For example, the case where an IP address to be registered is xe2x80x9c8. 0. 0. 0xe2x80x9d having a prefix length xe2x80x9c1xe2x80x9d will now be described. Among bit strings of entry address, all divisional bit strings of eight upper bits having xe2x80x9c1xe2x80x9d in the first bit indicate the registrable range in this case. In other words, entries ranging from xe2x80x9c128 (=1000 0000). 0. 0. 0xe2x80x9d to xe2x80x9c255 (=1111 1111). 0. 0. 0xe2x80x9d become the registrable range.
For example, the case where an IP address to be registered is xe2x80x9c8. 0. 0. 0xe2x80x9d having a prefix length xe2x80x9c2xe2x80x9d will now be described. Among bit strings of entry address, all divisional bit strings of eight upper bits having xe2x80x9c10xe2x80x9d in first and second bits indicate the registrable range in this case. In other words, entries ranging from xe2x80x9c128 (=1000 0000). 0. 0. 0xe2x80x9d to xe2x80x9c191 (=1011 1111). 0. 0. 0xe2x80x9d become the registrable range.
With respect to the registrable range, update control is conducted (S2 of FIG. 4), More specifically, if an entry having an IP address already registered is not included in entries in the registrable range determined at the step S1, then entries in the range are updated to new IP addresses, the transmission interface is also updated, and then the registration is finished.
If an entry having an IP address already registered is included in the range, then the prefix length of the already registered IP address is first compared with the prefix length of an IP address to be newly registered. If the prefix length of the already registered IP address is equal to or longer than the new prefix length, then the already registered contents are made intact and the registration is finished.
On the other hand, if the prefix length of the already registered IP address is shorter than the new prefix length then contents of entries in the range are updated to information of the IP address to be newly registered, the transmission interface is also updated, and the registration is finished.
FIG. 5 shows a procedure for registering an IP address in the case where the prefix length of an IP address to be registered is longer than 8 bits and is not longer than 16 bits in 32 bits. In this case, the registration is performed only for the retrieval table at the first stage (first control table) and the retrieval table at the second stage (second control table).
In registering, retrieval is first conducted in the first control table by using the divisional bit string value of eight upper bits (step S1 of FIG. 5), which is the same way as the step S1 of FIG. 4.
It is then determined whether an already registered entry is included in the pertinent bits of the first control table (step S2 of FIG. 5).
If an already registered entry is included, then the second control table Indicated by the already registered entry is accessed (step S3 of FIG. 5).
On the other hand, If an already registered entry is not included, then a new second control table is selected and set according to a new next table pointer (step S4 of FIG. 5). In succession, the new second control table is accessed (step S5 of FIG. 5).
In the second control table, a registrable range is determined (step S6 of FIG. 5) in the same way as the step S1 of FIG. 4. Subsequently, update control is conducted for the registrable range (step S7 of FIG. 5) in the same way as the step S2 of FIG. 4, and the registration is finished.
In the conventional expansion method, if new required information to be sent to the next forwarding destination is added, then the added information itself. In addition to information such as transmission interface, is set in every registrable entry.
Also in the case where the prefix length of an IP address to be registered is longer than 16 bits and not longer than 24 bits, and in the case where the prefix length of the IP address to be registered is longer than 24 bits and not longer than 32 bits, entry setting can be performed in the same way.
Also in the case where an already registered IP address is to be deleted, information such as the transmission interface registered in all pertinent entries of the retrieval table is deleted in the same way as the case of addition.
In the above-described expansion method, however, there has been a problem such that changes of registered address (including addition, updating, and deletion) become complicated because the retrieval tables are divided into a plurality of stages and one registered address is registered in a plurality of entries by means of expansion of bit strings.
In other words, typically in the conventional expansion method, contents of a plurality of entries must be changed in order to register or delete one IP address. For example, for deleting the registration of the registered address xe2x80x9cP2xe2x80x9d in the example shown in FIG. 3, the registered address xe2x80x9cP2xe2x80x9d must be deleted in the four entries xe2x80x9c100,xe2x80x9d xe2x80x9c101,xe2x80x9d xe2x80x9c110,xe2x80x9d and xe2x80x9c111xe2x80x9d of the retrieval table at the second stage.
If a retrieval table at a stage corresponding to the IP address to be newly registered is not present, then a retrieval table at one stage must be purposely added in the expansion method in order to register one IP address. In addition, it also becomes necessary to write the same registered information such as the transmission interface into each of the pertinent entries of the retrieval table.
Further, according to the conventional expansion method, a plurality of retrieval tables are provided in the second and subsequent stages so as to individually correspond to the registered entries of a retrieval table at the immediately preceding stage. As a result, a large number of retrieval tables are needed. Accordingly, the capacity of a memory for storing the retrieval tables becomes large.
In addition, in the conventional expansion method, it is necessary to form a retrieval table at one stage even if the retrieval table has only one entry having a destination address registered therein. Therefore, the conventional expansion method has a problem that the memory capacity is wasted.
In order to save the memory capacity, it is conceivable to provide each retrieval table with a variable length according to the number of entries. If the retrieval tables are made variable, however, then it becomes difficult to manage and control the retrieval tables and, in particular, it becomes difficult to implement the retrieval tables by using hardware.
The present invention has been made in order to solve the problems as described above.
An object of the present invention is to provide a forwarding information retrieval method and apparatus allowing memory capacity saving and easy change of registered addresses.
According to the present invention, an improved method for retrieving a hop pointer from a retrieval table using a destination address of a received data signal as a retrieval key to determine a next forwarding destination of the received data signal is provided. First, a plurality of first tables and a second table are stored in the retrieval table. The first tables are hierarchically arranged according to division of the destination address, an entry of each of the first tables including a second-table pointer indicating a next accessed second entry of the second table. The second table serves as an index table of the first tables, wherein each of entries of the second table includes a hop pointer and a first-table pointer indicating a next accessed first table. The second table and a selected one of the first tables are alternately accessed depending on a first-table pointer included in an accessed entry of the second table while retrieving an entry of an accessed first table using a corresponding divisional portion of the destination address. In this manner, a hop pointer is read from a finally accessed entry of the second table as a retrieval result.
As described above, hop pointers each indicating next forwarding destinations are stored only in the second table and the first tables have only second table pointers as entries. Therefore, the memory capacity forming an enormous number of first tables can be dramatically reduced as compared with the memory capacity of an individual retrieval table. In other words, the memory capacity of the retrieval tables can be saved as a whole.
Further, in the present invention, hop pointers are stored only in the second table serving as an index. In alteration of a registered address, therefore, it is sufficient to change only the second table pointer regarding an enormous number of pertinent entries of the first tables Alteration of information concerning the forwarding destination, such as the hop pointer can be conducted only in the second table. In the present invention, therefore, registered address alteration can be conducted easily.
According to an aspect of the present invention, a method for retrieving a hop pointer from a retrieval table using a destination address of a received data signal as a retrieval key to determine a next forwarding destination of the received data signal, the hop pointer indicating a registered address of the next forwarding destination, the method comprising the steps of:
a) providing a plurality of first tables T1_i (i is a positive integer) and a second table T2 in the retrieval table, wherein the plurality of first tables are hierarchically divided into a plurality of stages S(j) (j is a positive integer) corresponding to a sequence of divisional bit strings obtained by sequentially dividing a predetermined bit length of the destination address in decreasing order of significance, each of the first tables containing at least one first entry E1_k (k is a positive integer) each having a different offset address numbered based on a corresponding divisional bit string, wherein a first entry having an off set address matching a bit string portion of a registered address corresponding to a stage of each of the first tables includes a second-table pointer wherein the second table has a plurality of second entries E2_m (m is a positive integer), each of which includes a retrieval control flag, a first-table pointer, and a hop pointer, wherein one of the second entries is indicated by a second-table pointer of the first table, wherein the first-table pointer indicates a first table of a stage S(j+1) following a current stage S(j):
b) dividing the destination address into a plurality of destination divisional bit strings DST(j) each corresponding to the stages S(j);
c) accessing a first table T1_l of the stage S(1) to retrieve a first entry E1_l using a high-order destination divisional bit string DST(1) corresponding to the stage S(1) as a retrieval key, wherein the first entry E1_1 has an offset address matching the high-order destination divisional bit string DST(1);
d) accessing a second entry E2_l of the second table T2 according to a second-table pointer included in the first entry E1_l;
e) when a retrieval control flag included in a second entry E2_m indicates continuation of retrieval, accessing a first table T1_i indicated by a first-table pointer included in the second entry E2_m to retrieve a first entry E1_k from the first table T1_i using a destination divisional bit string of a stage corresponding to the first table T1_i as a retrieval key, wherein the first entry E1_k has an offset address matching the destination divisional bit string of a stage corresponding to the first table T1_i;
f) accessing another second entry E2_m of the second table T2 according to a second-table pointer included in the retrieved first entry E1_k:
g) repeating the steps (a) and (f) when a retrieval control flag included in a second entry E2_m indicates continuation of retrieval; and
h) when a retrieval control flag included in a second entry E2_m indicates termination of retrieval, reading a hop pointer included in the second entry E2_m as a retrieval result to terminate the retrieval.
Each of the second entries of the second table may further include an update flag indicating whether a hop pointer is updated. An initial hop pointer is stored in a variable. In the step (f), when an update flag included in the second entry E2_m indicates updating of a hop pointer, updating the variable to a hop pointer included in the second entry E2_m. In the step (h), when a retrieval control flag included in the second entry E2_m indicates termination of retrieval, reading a hop pointer from the variable as a retrieval result to terminate the retrieval.
According to another aspect of the present invention, the plurality of first tables are hierarchically divided into a plurality of stages S(j) (j is a positive integer) corresponding to a sequence of divisional bit strings obtained by sequentially dividing a predetermined bit length of the destination address in decreasing order of significance, each of the first tables containing at least one first entry E1_k (k is a positive integer) each having a different offset address numbered based on a corresponding divisional bit string, wherein a second-table pointer is included in a first entry which has an offset address matching a bit string portion of a registered address corresponding to a stage of each of the first tables when updating a hop pointer is needed, and wherein a first-table pointer indicating a first table of a stage S(j+1) following a current stage S(j) is included in a first entry which has an offset address matching a bit string portion of a registered address corresponding to a stage of each of the first tables when updating a hop pointer is not needed. The second table has a plurality of second entries E2_m (m is a positive integer), each of which includes a retrieval control flag, a first-table pointer, and a hop pointer, wherein one of the second entries is indicated by a second-table pointer of the first table, wherein the first-table pointer indicates a first table of a stage S(j+1) following a current stage S(j). The method includes the steps of: b) dividing the destination address into a plurality of destination divisional bit strings DST(j) each corresponding to the stages S(j); c) accessing a first table T1_1 of the stage S(1) to retrieve a first entry E1_1 using a high-order destination divisional bit string DST(1) corresponding to the stage S(1) as a retrieval key, wherein the first entry E1_1 has an offset address matching the high-order destination divisional bit string DST(1): d) accessing a second entry E2_1 of the second table T2 according to a second-table pointer included in the first entry E1_1: e) when a retrieval control flag included in a second entry E2_m indicates continuation of retrieval, accessing a first table T1_1 indicated by a first-table pointer included in the second entry E2_m to retrieve a first entry E1_k from the first table T1_i using a destination divisional bit string of a stage corresponding to the first table T1_i as a retrieval key, wherein the first entry E1_k has an offset address matching the destination divisional bit string of a stage corresponding to the first table T1_i; f) when a retrieved first entry E1_k includes a first-table pointer, directly accessing a first table T1_i indicated by a first-table pointer included in the retrieved first entry E1_k without accessing the second table to retrieve a first entry E1_k from the directly accessed first table T1_k using a destination divisional bit string of a stage corresponding to the directly accessed first table T1_i as a retrieval key; g) accessing another second entry E2_m of the second table T2 according to a second-table pointer included in the retrieved first entry E1_k; h) repeating the steps (e) and (g) when a retrieval control flag included in a second entry E2_m indicates continuation of retrieval, and i) when a retrieval control flag included in a second entry E2_m indicates termination of retrieval, reading a hop pointer included in the second entry E2_m as a retrieval result to terminate the retrieval.
Therefore, when a retrieved first entry includes a first-table pointer, a first table indicated by a first-table pointer included in the retrieved first entry can be directly accessed without accessing the second table, resulting in rapid retrieving operation and further reduced memory capacity of the second table.
Each of the first tables is preferably one of a bit-0 first table and a bit-1 first table. When a head bit of a divisional bit string corresponding to the first table is 0, the bit-0 first table corresponds to a remaining divisional bit string obtained by removing the head bit of 0 from the divisional bit string corresponding to the first table. When a head bit of a divisional bit string corresponding to the first table is 1, the bit-1 first table corresponds to a remaining divisional bit string obtained by removing the head bit of 1 from the divisional bit string corresponding to the first table. In this case, each of the second entries of the second table further includes a bit-0 first table pointer and a bit-1 first table pointer. In the step (e), when a head bit of a corresponding divisional bit string is 0, a bit-0 first table indicated by a bit-0 first table pointer is accessed and, when a head bit of a corresponding divisional bit string is 1, a bit-1 first table indicated by a bit-1 first table pointer is accessed.
By preparing a bit-1 first table and a bit-0 first table for each first table of each stage, either of them can be omitted, resulting in further reduced memory capacity of the first tables. Further, one of the bit-1 and bit-0 first tables is selected and searched depending on the head bit of the destination divisional bit string, resulting in half the number of searched entries.